package problems.contest;

import java.util.Arrays;

/**
 * <p></p>
 *
 * @author habitplus
 * @since 2023/2/12 10:27
 */
public class WCT332 {

    /**
     * T1|
     * <p></p>
     */
    public long findTheArrayConcVal(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        long ans = 0;

        while (l <= r) {
            if (l == r) {
                ans += nums[l];
                break;
            }
            String add = nums[l] + String.valueOf(nums[r]);
            ans += Long.parseLong(add);
            ++l;
            --r;
        }
        return ans;
    }



    public long countFairPairs(int[] nums, int lower, int upper) {
        int n = nums.length;
        int j1, j2;
        long ans = 0;
        Arrays.sort(nums);
        for (int i = 0; i < n - 1; ++i) {
            // 找 >= lower-nums[i] 的最小的数
            j1 = findMin(nums, i + 1, n - 1, lower - nums[i]);
            // 找 <= upper-nums[i] 的最大的数
            j2 = findMax(nums, i + 1, n - 1, upper - nums[i]);
//            if (j2 >= n || nums[j2] > upper - nums[i]) --j2;
            System.out.println("==>\t" + j1 + " " + j2);

            ans += (j2 - j1);
        }

        return ans;
    }

    private int findMin(int[] nums, int l, int r, int target) {
        // l <= r
        int mid;
        while (l < r) {
            mid = (l + r) / 2;
            if (nums[mid] >= target) r = mid + 1;
            else l = mid;
        }

        return l;
    }

    private int findMax(int[] nums, int l, int r, int target) {
        int mid;
        while (l <= r) {
            mid = (l + r) / 2;
            if (nums[mid] <= target) l = mid + 1;
            else r = mid;
        }

        return l;
    }


    public static void main(String[] args) {
        System.out.println(new WCT332().countFairPairs(new int[] {0,0,0,0,0,0}, 0, 0));
    }
}
